package DFS_BFS;

/**
 * @PackageName: DFS_BFS
 * @ClassName: LeetCode463
 * @Author: chen jinxu
 * @Date: 2022/8/9 23:32
 * @Description: //岛屿的周长
 *
 *  给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域
 * 网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，
 * 一个或多个表示陆地的格子相连组成的岛屿）。
 * 岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。
 * 格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长
 *
 * 输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
 * 输出：16
 * 解释：它的周长是上面图片中的 16 个黄色的边
 *  输入：grid = [[1]]
 * 输出：4
 * 输入：grid = [[1,0]]
 * 输出：4
 *
 * row == grid.length
 * col == grid[i].length
 * 1 <= row, col <= 100
 * grid[i][j] 为 0 或
 */
public class LeetCode463 {
    public static void main(String[] args) {
        System.out.println(islandPerimeter(new int[][]{{0,1,0,0},{1,1,1,0},{0,1,0,0},{1,1,0,0}}));
    }

    public static int islandPerimeter(int[][] grid) {
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == 1) {
                    return dfs(grid, r, c);
                }
            }
        }
        return 0;
    }
    static int dfs(int[][] grid, int r, int c) {
        // 一个格子为岛屿的话，它每与一个边界或者水域 挨着，边长增加1
        // 边界
        if (!(0 <= r && r < grid.length && 0<= c && c < grid[0].length)) {
            return 1;
        }
        // 为水域
        if (grid[r][c] == 0) {
            return 1;
        }
        // 走过的区域返回，不再向下走
        if (grid[r][c] != 1) {
            return 0;
        }
        // 记录已经走过，避免重复遍历
        grid[r][c] = 2;
        return dfs(grid, r + 1, c) + dfs(grid,r- 1, c) + dfs(grid, r, c + 1) + dfs(grid, r, c - 1);
    }
}
